#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int Maxn=1e5+6;
const int Mod=111121,inv2=(Mod+1)/2;
int n;
int val[Maxn];
vector<int>e[Maxn];
bool vis[Maxn];

ll ans,ret;

inline ll ksm(ll a,int b,int mod){
    if(!a) return 0;
    ll z=1;
    while(b){
        if(b&1) z=z*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return z;
}

void dfs(int u,int now,int val1,int val2){
    vis[now]=1;
    if(u!=now) ans=(ans+ksm(val2,val1,Mod))%Mod;
    else ret=(ret+ksm(val2,val1,Mod))%Mod;
    for(auto v:e[now]){
        if(!vis[v]){
            dfs(u,v,val1|val[v],val2&val[v]);
        }
    }
}

int main(){
    freopen("abstract.in","r",stdin);
    freopen("abstract.out","w",stdout);

    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&val[i]);
    for(int i=1;i<n;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        e[u].emplace_back(v);
        e[v].emplace_back(u);
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++) vis[j]=0;
        dfs(i,i,val[i],val[i]);
    }
    printf("%lld",(ans*inv2%Mod+ret)%Mod);

    system("pause");
    return 0;
}
/*
10
912462448 906453427 509376669 201292891 980414095 197813063 390849362 839702565 723809664 652482951
2 1
3 1
4 2
5 4
6 3
7 5
8 7
9 8
10 9

*/